package jjn.geektime;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Jjn
 * @since 2023/7/17 19:08
 */
public class LRUCache {
    
    static class Node {
        public Node pre;
        public Node next;
        public int key;
        public int value;
    }
    
    private final int capacity;
    private final Node head;
    private final Node tail;
    private final Map<Integer, Node> map;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>(capacity + 8);
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        if (!this.map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        this.removeFromList(node);
        this.insertIntoListHead(key, node.value);
        return node.value;
    }
    
    public void put(int key, int value) {
        if (this.map.containsKey(key)) {
            Node node = this.map.get(key);
            this.removeFromList(node);
            this.insertIntoListHead(key, value);
        } else {
            this.insertIntoListHead(key, value);
        }
        if (map.size() > this.capacity) {
            this.removeFromList(tail.pre);
        }
    }
    
    private void insertIntoListHead(int key, int value) {
        Node node = new Node();
        node.key = key;
        node.value = value;
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
        this.map.put(key, node);
    }
    
    private void removeFromList(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        this.map.remove(node.key);
    }
    
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(4);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        lruCache.put(4, 4);
        System.out.println("lruCache.get(1) = " + lruCache.get(1));
        lruCache.put(5, 5);
        lruCache.put(6, 6);
        System.out.println("lruCache.get(3) = " + lruCache.get(3));
        System.out.println("lruCache.get(2) = " + lruCache.get(2));
    }
    
}
